Due to the proliferation of micro-computers distributed processing systems have become commonplace. In such a system the data processing functions are spread over a number of separate data processing machines. Each of the machines performs part of the overall processing task and data and results are passed between the machines by means of data links. In many environments a distributed processing system poses a problem for data integrity and security because sensitive data must be transmitted between the separate data processing machines over transmission facilities, such as telephone lines, which are far from secure. In other cases, a centralized data processing facility may have the capability of being accessed from many outlying locations by means of data terminals over dedicated data lines or public telephone lines.
Such systems are prone to to misuse from a variety of sources such as illicit access to the system by computer "hackers" or disgruntled employees and improper disclosure or modification of stored information by unscrupulous competitors.
To protect the privacy of data communications and to prevent improper modification of data exchanged between two processing locations over insecure communication networks, a number of prior art methods and apparatus have been developed. One general category of prior art data security systems are password systems. These systems require the entry of a password before they will allow access to a secure data processing installation. Password systems are simple to implement but are also easy to circumvent. For a price, any password can be obtained, or passwords can be guessed.
A second category of prior art security systems are called automatic call back systems. In operation, call-back systems respond to an incoming phone call by requesting a user identification code. In response, the user enters his secret code. After receiving the code the call-back system terminates the call. The identification code is looked up in an directory to find an associated call-back telephone number and then a return call is placed to the call-back number.
The call-back system eliminates illicit access by most casual hackers, but suffers from a number of problems. Callers must always call into the computer from a fixed telephone number which is stored in the system, therefore, salesmen and others who are mobile are precluded from remote access. Another problem is that the system is not immune to illicit entry by means of telephone line taps, or redirection of a line through call forwarding.
Due to the above problems, variations of call back systems have been developed in the art. One such variation, in addition to the normal call back operation, can also operate with a special modem which sends an identity code to the central site when prompted by the central site controller. This latter variation allows remote access by mobile personnel who can carry the modem with them. However, the system is less secure than the simple call-back system since the identification code sent down the line by the modem can be intercepted by a line tap.
To avoid the previous problems with password and call-back systems, cryptographic techniques are becoming more frequently utilized by commercial organizations. These systems modify a message to produce another message which is unintelligible except to those persons possessing proper decoding equipment. In particular, most encryption systems use mathematical algorithms to convert between ordinary messages called "plain text" and encoded messages called "cipher text". The encoding or encrypting algorithm used to convert the plain text into a cipher text is chosen such that it is possible to retrieve the plain text when given the cipher text. To change the cipher text back into the plain text a decoding or decrytping algorithm is used which may be the same or different from the encoding algorithm.
The are two generally used types of cryptographic algorithms: block ciphers and stream ciphers. With block cipher encoding all plain text messages to be encrypted are divided up into "blocks" of text which are equally long. The encoding algorithm is applied to each block without taking encodings of previous or subsequent blocks into account. The second encoding method is stream cipher encoding in which each single character in the plain text message is encoded separately but the output of the encryption algorithm depends not only on the character to be encrypted, but also on the outputs of the encryption algorithm produced by encryption of the previous characters.
Both encryption methods have advantages, but the main reason for using stream cipher encoding is that it is more secure than block encoding. In particular with block encoding the sam plain text always produces the same cipher text each time it is passed through the encoding system. Thus, it is easier to "crack" the code if enough cipher text can be intercepted. With stream ciphers, decoding the same plain text produces different cipher text each time the text is passed through the system.
Since many users want to encode not only one message but many and since the intended recipients of the messages are frequently different, a new encoding algorithm cannot be used for each message or for each of the recipients as this would quickly become highly impractical. Consequently, in practical encryption systems, one encoding algorithm is used with many different parameters, called "keys", instead of many different algorithms. Thus, the key becomes another input, or argument, to the encoding algorithm along with the plain text message characters. In such systems, a decoding key is often required as an additional input to the decoding algorithm with the cipher text in order to be able to reproduce the plain text.
In the more complicated encryption systems, the encoding algorithms are publicly known but the encoded message cannot be recovered from the cipher text without knowledge of the decoding key. Thus, such cryptographic systems are attractive because they do not require that the entire system be kept secure, only the encoding and decoding keys.
The most popular method of encryption in the United States, is the so-called "Data Encryption Standard" or D.E.S. The operation and theory of this encryption method is well known and discussed in detail in Federal Information Processing Standard (FIPS) publication No. 46, and U.S. Pat. No. 3,958,081. The basic algorithm set forth in the D.E.S. publications (the D.E.S. algorithm) uses a key consisting of 56 digital bits, and performs a non-linear encoding or decoding of eight bytes (each byte is a digital coding of one plain text character) of data presented to it. To construct a system which uses the basic D.E.S algorithm several techniques are often utilized, some of which have added benefits such as the avoidance of synchronization problems between the encoding and decoding sites and the enhancement of overall security.
FIPS publication No. 81 describes several standardized encryption systems which use the basic D.E.S. algorithm. The simplest technique disclosed is called "Electronic Code Book". This technique is basically a block encoding scheme in which eight bytes (characters) of plain text are passed through a circuit which performs the D.E.S. encryption algorithm to yield eight bytes (characters) of cipher text. At the receiving end, eight bytes of cipher text are processed by a D.E.S. decoding circuit to reproduce the original eight bytes of plain text.
The Electronic Code Book technique has several undesirable properties. More particularly, in addition to security problems as discussed above with respect to block cipher codes, Electronic Code Book systems suffer from synchronization problems if the cipher text is sent to a remote location. In this case it is possible that the decoding receiver can lose time synchronization with the encoding transmitter, that is, the number of bits received doesn't equal the number of bits transmitted due to noise or problems with the communication line between the transmitting site and the receiving site. If no additional synchronization means are provided, then the transmitter and receiver may remain permanently out of synchronization and must eventually be manually resynchronized. When the transmitter and receiver are out of synchronization the data delivered by the receiver to the ultimate recipient, is completely erroneous.
For those systems which must avoid the obvious problems associated with the Electronic Code Book technique, FIPS publication No. 81 also discloses other more complicated schemes. These schemes are forms of stream ciphers which utilize a combination of past computed outputs and current inputs in a feedback arrangement whereby either encrypted data is fed back as in input to the encryption circuit along with the plain text (Cipher Feedback schemes), or the output of the encryption circuit is fed back as an input to the encryption circuit and the plain text is logically combined with the output of the encryption circuit (Output Feedback schemes).
Both Cipher Feedback and Output Feedback techniques disclosed in FIPS publication No. 81 eliminate the problem of the generation of the same cipher text for a given plain text, however only Cipher Feedback schemes solve the synchronization problem. Cipher Feedback schemes have the property that even if cipher text data is corrupted in transmission or received in error, the receiver will eventually resynchronize to the transmitted data stream, typically within a predetermined number of symbols sent or within a predetermined time period.
The price paid for the added synchronization benefits of the Cipher Feedback technique is added complexity of the encoding and decoding circuitry to handle the increased processing rates which occur. For example, when executing the Electronic Codebook technique, the D.E.S. algorithm needs to be executed only once per 8 bytes (characters) of data processed. However, in a typical Cipher Feedback system in which bytes of data are fed back to the encoding or decoding algorithm, the algorithm must be executed once per byte processed, or eight times as often as the Electronic Codebook technique. In Cipher Feedback systems in which each bit of the data is fed back, the D.E.S. algorithm must be executed once per bit processed, or 64 times as often as Electronic Codebook technique for the same eight bytes of data.
An additional undesirable aspect of Cipher Feedback techniques is "error extension". Because of the receiver's dependency on previously received data to decrypt current and future data, one symbol of data received in error typically causes a predetermined number of subsequent symbols to be decrypted erroneously. In high-error-rate conditions, such as commonly encountered with dial telephone lines, error extension may cause either a serious decrease in message transmission throughput (if error detection and retransmission of erroneously received data is utilized) or in reliability (in the absence of any error detection scheme).
Another consideration which has limited the popularity of these latter stream cipher encryption techniques disclosed in FIPS publication No. 81 is cost. Typically, special purpose integrated circuits must be included in the communications system to perform the encoding and decoding operations. Due to the large number of operations required to send ordinary text in a relatively secure fashion at a reasonable transmission speed, these special purpose circuits are complex and expensive.
Accordingly, it is an object of this invention to provide an encryption technique which performs the necessary encoding and decoding operations in a manner more efficient than prior art encryption systems.
It is another object of this invention to provide an encryption technique which will automatically detect and correct for loss of synchronization.
It is yet another object of this invention to provide an encryption technique which eliminates the problem of error extension inherent to Cipher Feedback.
It is still another object of this invention to provide an encryption technique which has the property that the same plain text input data does not yield the same cipher text.
It is a further object of this invention to provide an encryption technique has a computational complexity that is similar to that required by block encryption techniques.
It is another object of this invention to provide an encryption technique which can be implemented with relatively low cost circuitry.
It is still a further object of this invention to provide an encryption technique which ensures that messages which are damaged in transmission or storage, and are erroneously accepted by the receiving or retrieving apparatus due to an error detection code which is accepted as valid, will not cause a loss of synchronization.